package org.laizili.solution.nowcodertop101.list;

import org.laizili.structure.list.ListNode;

/**
 * <a href="https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&sfm=html&channel=nowcoder">BM3. 链表中的节点每k个一组翻转</a>
 * <p>
 * tags: 链表
 * <p>
 * notes: 链表步进计数; 前驱结点指针; 边界
 */
public class BM3 {

    /**
     * 迭代解法
     */
    private static class Solution {
        /**
         * @param head ListNode类
         * @param k    int整型
         * @return ListNode类
         */
        public ListNode reverseKGroup(ListNode head, int k) {
            // write code here
            if (head == null || k == 1) {
                return head;
            }
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode cursor = head;
            ListNode segHead = dummy, segTail;
            while (cursor != null) {
                int n = 0;
                for (; cursor != null && n < k; n++) {
                    cursor = cursor.next;
                }
                if (n < k) {
                    break;
                }
                // reverse
                segTail = segHead.next;
                ListNode bound = cursor;
                while (segTail.next != bound) {
                    ListNode moved = segTail.next;
                    segTail.next = moved.next;
                    moved.next = segHead.next;
                    segHead.next = moved;
                }
                segHead = segTail;
            }
            return dummy.next;
        }
    }

    /**
     * 递归解法
     */
    private static class Solution2 {
        /**
         * @param head ListNode类
         * @param k    int整型
         * @return ListNode类
         */
        public ListNode reverseKGroup(ListNode head, int k) {
            // write code here
            ListNode tail = head;
            for (int i = 0; i < k; i++) {
                if (tail == null) {
                    return head;
                }
                tail = tail.next;
            }
            ListNode prev = null;
            ListNode cur = head;
            while (cur != tail) {
                ListNode tmp = cur.next;
                cur.next = prev;
                prev = cur;
                cur = tmp;
            }
            head.next = reverseKGroup(tail, k);
            return prev;
        }
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
//        ListNode newHead = new Solution().reverseKGroup(node1, 2);
        ListNode newHead = new Solution2().reverseKGroup(node1, 4);
        while (newHead != null) {
            System.out.println(newHead.val);
            newHead = newHead.next;
        }
    }
}
